import java.util.Scanner;
 
public class matrix {
    public static void main (String[] args) {
        // Declare static variables
        int numMatrices;
        Scanner scan = new Scanner(System.in);
         
         
        // Introduce the program
        System.out.println ();
        System.out.println ("=========================================================");
        System.out.println ();
        System.out.println ("Java Matrix Chain Multiplication Dynamic Solution Program");
        System.out.println ();
        System.out.println ("=========================================================");
        System.out.println ();
         
        System.out.println ("This program solves the problem of the order in which to");
        System.out.println ("multiply matrices to minimize the amount of work. It does");
        System.out.println ("so using dynamic programming.");
        System.out.println ();
        System.out.println ("Copyright (c) 2012 Jonathan Landrum. All Rights Reserved.");
        System.out.println ();
        System.out.println ("---------------------------------------------------------");
        System.out.println ();
         
        System.out.print   ("How many matrices do you want to multiply? ");
        numMatrices = scan.nextInt();
         
         
        // Declare dynamic variables (Size changes based on input)
        char[] matrices = new char[numMatrices];
         
        for (int i = 0; i < numMatrices; ++i)
            matrices[i] = (char)(i + 65);
         
        String[][] output = new String[numMatrices][numMatrices];
        double[][] matrix = new double[numMatrices][numMatrices];
         
        for (int i = 0; i < numMatrices; ++i)
            output[i][i] = Character.toString(matrices[i]);
         
        for (int i = 0; i < numMatrices; ++i)
            matrix[i][i] = 0;
         
        int[] dimension = new int[numMatrices + 1];
         
        System.out.print  ("What is the height of matrix 1? ");
        dimension[0] = scan.nextInt();
         
        for (int i = 1; i < dimension.length; ++i) {
            System.out.print ("What is the width of matrix " + i + "? ");
            dimension[i] = scan.nextInt();
        }
         
         
        // Showtime
        System.out.println ();
        System.out.println ("Processing...");
        System.out.println ();
        for (int b = 1; b < numMatrices; ++b) {
            for (int i = 0; i < numMatrices - b; ++i) {
                int j = i + b;
                matrix[i][j] = Double.POSITIVE_INFINITY;
                for (int k = i; k < j; ++k) {
                    if (matrix[i][j] > matrix[i][k] + matrix[k + 1][j] + 
                        dimension[i] * dimension[k + 1] * dimension[j + 1])
                        output[i][j] = "(" + output[i][k] + output[k + 1][j] + ")";
                    matrix[i][j] = Math.min(matrix[i][j], matrix[i][k] + matrix[k + 1][j] + 
                    dimension[i] * dimension[k + 1] * dimension[j + 1]);
                }
            }
        }
         
         
        // Return results
        System.out.println ("Using parenthesization " + output[0][numMatrices - 1] + 
                            " will take " + (int)matrix[0][numMatrices - 1] + " calculations.");
        System.out.println ();
        System.out.println ("---------------------------------------------------------");
        System.out.println ("\\\\//_ Live long and prosper.");
    }
}
